#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int strStr(char* haystack, char* needle);
int* getNext(char* pattern);

int main()
{
	return 0;
}

int strStr(char* haystack, char* needle)
{
	if (!needle[0]) return 0;
	if (!haystack[0]) return -1;

	int* next = getNext(needle);
	int idx1 = 0, idx2 = 0;
	char ch1, ch2;
	while ((ch1 = haystack[idx1]) && (ch2 = needle[idx2])) {
		if (ch1 == ch2) {
			idx1++;
			idx2++;
		} else if (!~next[idx2])
			idx1++;
		else
			idx2 = next[idx2];
	}

	return needle[idx2] ? -1 : idx1 - idx2;
}

int* getNext(char* pattern)
{
	int length = strlen(pattern);
	int* next = calloc(length, sizeof(int));
	next[0] = -1;
	if (length == 1) return next;
	next[1] = 0;

	int i = 2, cn = 0;
	while (pattern[i]) {
		if (pattern[i - 1] == pattern[cn])
			next[i++] = ++cn;
		else if (cn > 0)
			cn = next[cn];
		else
			next[i++] = 0;
	}

	return next;
}
